package company.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 打打印了图一条路径
 */
public class GraphLa {
    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.add(0, 1);
        graph.add(0, 2);
        graph.add(1, 3);
        graph.add(1, 4);
        graph.add(2, 5);
        graph.add(2, 6);
        graph.add(3, 7);
        graph.add(4, 7);
        graph.mainWay(0, 7);

    }

}

class Graph {
    private int point;
    private List<Integer> neighterList[];

    Graph(int point) {
        this.point = point;
        this.neighterList = new ArrayList[point];
        for (int i = 0; i < point; i++) {
            neighterList[i] = new ArrayList<>();
        }
    }

    public void add(int begin, int end) {
        neighterList[begin].add(end);
        neighterList[end].add(begin);
    }

    public void initRouter(int[] router) {
        for (int i = 0; i < router.length; i++) {
            router[i] = -1;
        }
    }

    public void mainWay(int begin, int end) {
        if (begin == end) {
            return;
        }
        Deque<Integer> deque = new LinkedList<>();
        deque.offer(begin);
        boolean[] visited = new boolean[point];
        visited[begin] = true;
        int[] prev = new int[point];
        initRouter(prev);
        while (!deque.isEmpty()) {
            Integer poll = deque.poll();
            List<Integer> currNeighterList = neighterList[poll];
            for (int i = 0; i < currNeighterList.size(); i++) {
                Integer currNeighter = currNeighterList.get(i);
                if (!visited[currNeighter]) {
                    if (currNeighter != end) {
                        prev[currNeighter] = poll;
                        visited[currNeighter] = true;
                        deque.offer(currNeighter);
                    } else {
                        prev[currNeighter] = poll;
                        printGraph(prev, begin, end);
                        return;
                    }
                }
            }

        }
    }

    private void printGraph(int[] prev, int begin, int end) {
        if (prev[end] != -1 && begin != end) {
            printGraph(prev, begin, prev[end]);
        }
        System.out.print(end + ">>");
    }

}
